package com.itHsuSE.demo2;

class T{
    //使用递归回溯的思路解决老鼠出迷宫

    /**
     * 1、findway 方法就是专门来找出迷宫的路径
     * 2、@param map 迷宫
     * 3、@param i 老鼠的位置的横坐标
     * 4、@param j 老鼠的位置的纵坐标
     *          初始化位置为（1,1）
     *          5、因为是递归找路，所以先规定map数组的各个值的含义
     *          6、 0 表示可以走，1 表示不可以走，2 表示可以走，3表示走过，但是是死路
     *              当map[6][5] == 2 时表示找到通路就可以结束了，否则就继续找
     *          7、先确定老鼠的找路策略，下->右->上->左
     * @return 能找到返回true 否则返回false
     */
    public boolean findWay(int[][] map,int i,int j){
        if(map[6][5]==2){//说明找到
            return true;
        }else {
            if(map[i][j]==0){//当前这个位置0说明可以走
                //我们假定可以走通
                map[i][j]=2;
                //使用找路策略，来确定是否真的可以走通
                //下->右->上->左
                if(findWay(map,i+1,j)){//先走下
                    return true;
                }else if(findWay(map,i,j+1)){//右
                    return true;
                }else if(findWay(map,i-1,j)){//上
                    return true;
                }else if(findWay(map,i,j-1)){//左
                    return true;
                }else {//说明并不能走通
                    map[i][j]=3;
                    return false;
                }
            }else {//map[i][j]==1,2,3 这些都是走不通的
                return false;
            }
        }
    }
}

public class MiGong {
    public static void main(String[] args) {
        //思路
        //1、先创建迷宫，用二维数组表示：int[][] map=new int[8][7];
        //2、先规定map数组的元素值：0表示可以走，1表示不可以走
        int[][] map=new int[8][7];
        //3、将最上面和最下面一行全部设置为1
        for (int i = 0; i < 7; i++) {
            map[0][i]=1;//第一行
            map[7][i]=1;//第八行
        }
        //4、将最左边和最右边一列全部设置为1
        for (int i = 0; i < 8; i++) {
            map[i][0]=1;
            map[i][6]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        System.out.println("===当前地图情况===");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        T t1=new T();
        t1.findWay(map,1,1);

        System.out.println("===找路情况如下===");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}
